// var arr = [4, 23, 100, 9, 7, 49, 36, 57]
// console.log('初始数组', arr)

// 冒泡排序
// var arr = [4, 23, 100, 9, 7, 49, 36, 57]
// console.log('初始数组', arr)
// for (let i = 0; i < arr.length - 1; i++) {
//   for (let j = 0; j < arr.length - 1 - i; j++) {
//     let temp = null
//     if (arr[j] > arr[j+1]) {
//       temp = arr[j+1]
//       arr[j+1] = arr[j]
//       arr[j] = temp
//     }
//   }
//   console.log('第' + i + '次', arr)
// }
// console.log('最终', arr)


// 选择排序 时间复杂度 O(n*n) 空间复杂度 O(1) 稳定性 不稳定
// 首先从原始数组中找到最小的元素，并把该元素放在数组的最前面，然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，知道排序完毕。
// minIndex始终保存着最小值的位置的索引，随着i的自增，遍历的数组长度越来越短，直到完成排序。
// var arr = [4, 23, 100, 9, 7, 49, 36, 57]
// console.log('初始数组', arr)
// console.time('选择排序时间')
// for (let i = 0; i < arr.length; i++) {
//   let minIndex = i
//   for (let j = i + 1; j < arr.length; j++) {
//     if (arr[j] < arr[minIndex]) {
//       minIndex = j
//     }
//   }
//   let temp = null
//   temp = arr[i]
//   arr[i] = arr[minIndex]
//   arr[minIndex] = temp
//   console.log('第' + i + '次', arr)
// }
// console.timeEnd('选择排序时间')
// console.log('最终', arr)

// 插入排序
// 一般来说 插入排序都采用in-place在数组上实现
// 从第一个元素开始 该元素可以认为已经被排序
// 取出下一个元素 在已经排序的元素序列中从后向前扫描
// 如果该元素（已排序）大于新元素 将该元素移到下一位置
// 重复步骤3 直到找到已排序的元素小于或等于新元素的位置
// 将新元素插入到该位置后
// 重复步骤2-5
// var arr = [4, 23, 100, 9, 7, 49, 36, 57]
// console.log('初始数组', arr)

// function Insertion(arr) {
//   let len = arr.length
//   let preIndex, current
//   for(let i = 1; i < len; i++) { // 默认从i = 1开始判断
//     preIndex = i - 1 // 内部游标
//     current = arr[i] // 现在是第几项
//     while (preIndex >= 0 && current < arr[preIndex]) { // 如果当前项比前一项小的话
//       arr[preIndex + 1] = arr[preIndex] // 游标后一项等于游标项
//       preIndex-- // 游标前移
//     }
//     arr[preIndex + 1] = current // 由于游标已经减一  所以刚刚那一项也就是pre+1项  这一项需要变成当前项  至此  current向前比较了一位  然后继续循环
//   }
//   return arr
// }
// Insertion(arr)
// console.log('最终', arr)


// 快速排序
// 阮一峰老师的实现方法
// 思路：1、选择数组中间数作为基数，并从数组中取出此基数 2、准备两个数组容器，遍历数组，逐个与基数比对，较小的放在左边容器较大的放右边容器 3、递归处理两个容器的元素，并将处理后的数据与基数按大小合并成一个数组 返回

// var arr = [4, 23, 100, 9, 7, 49, 36, 57]
// console.log('初始数组', arr)

// var quickSort = function (arr) {
//   if (arr.length <= 1) { // 如果是空数组或者只有一个元素 则无需排序直接返回
//     return arr
//   }
//   var pivotIndex = Math.floor(arr.length / 2) // floor字面意思“地板” 11.5=11 -11.5=-12 往下减一
//   var pivot = arr.splice(pivotIndex, 1)[0]

//   var left = []
//   var right = []

//   for (var i = 0; i < arr.length; i++) {
//     if (arr[i] < pivot) {
//       left.push(arr[i])
//     } else {
//       right.push(arr[i])
//     }
//   }

//   return quickSort(left).concat([pivot], quickSort(right))
// }

// console.log('最终', quickSort(arr))